#define DEBUG
#pragma GCC optimize("-O2")
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int maxn=1000000, mods[2]={1000000007, 998244353};

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

ll pow[2][maxn+1];

void initPow(int n) {
  for (int t=0; t<2; t++) {
    pow[t][0] = 1;
    for (int i=1; i<=n; i++) {
      pow[t][i] = pow[t][i-1]*27%mods[t];
    }
  }
}

class HashTable {
public:
  static const int size=2000003;
  ll k[size][2];
  int val[size], ver[size], nowv;

  void init() {
    nowv++;
  }

  void set(ll k0, ll k1, int v) {
    int p=k0*k1%size;
    for (; ver[p]==nowv; p=(p+1)%size) {
      if (k[p][0]==k0 && k[p][1]==k1) {
        val[p] = v;
      }
    }
    k[p][0] = k0, k[p][1] = k1;
    val[p] = v;
    ver[p] = nowv;
  }

  int get(ll k0, ll k1) {
    int p=k0*k1%size;
    for (; ver[p]==nowv && (k[p][0]!=k0 || k[p][1]!=k1); p=(p+1)%size);
    return ver[p]==nowv ? val[p] : 0;
  }
};

HashTable hst;

class PTree {
public:
  int n, len[maxn+3], son[maxn+3][26], fail[maxn+3], ans[maxn+3];
  ll hash[maxn+3][2];

  void init() {
    n = 2;
    len[1]=-1, len[2]=0;
    fail[2] = 1;
    memset(son[1], 0, sizeof son[1]);
    memset(son[2], 0, sizeof son[2]);
  }

  int addChar(char *s, int p, int last) {
    for (; p<=len[last]+1 || s[p]!=s[p-len[last]-1]; last=fail[last]);
    int now;
    if (!son[last][s[p]-'a']) {
      now = son[last][s[p]-'a'] = ++n;
      memset(son[now], 0, sizeof son[now]);
      len[now] = len[last]+2;
      ans[now] = 0;
      if (len[now]==1) {
        fail[now]=2;
        hash[now][0]=hash[now][1]=s[p]-'a'+1;
      } else {
        for (int t=0; t<2; t++) {
          hash[now][t] = (hash[last][t]*27%mods[t]+(s[p]-'a'+1)*(pow[t][len[last]+1]+1)%mods[t])%mods[t];
        }
        int i;
        for (i=fail[last]; i>1 && !(son[i][s[p]-'a'] && s[p-len[i]-1]==s[p]); i=fail[i]);
        if (son[i][s[p]-'a'] && s[p-len[i]-1]==s[p]) {
          fail[now] = son[i][s[p]-'a'];
        } else {
          fail[now] = i;
        }
      }
      hst.set(hash[now][0], hash[now][1], now);
    } else {
      now = son[last][s[p]-'a'];
    }

    return now;
  }

  int solve() {
    int ret=0;
    for (int i=n; i>2; i--) {
      for (int j=0; j<26; j++) {
        if (son[i][j]) {
          ans[i]^=ans[son[i][j]];
        }
      }
      ret = max(ret, ans[i]);
    }
    return ret;
  }
};

void initStrHash(int n, char *s, ll hash[][2]) {
  hash[0][0] = hash[0][1] = 0;
  for (int i=1; i<=n; i++) {
    for (int t=0; t<2; t++) {
      hash[i][t] = (hash[i-1][t]*27%mods[t]+(s[i]-'a'+1))%mods[t];
    }
  }
}

void addP(PTree &tree, int o, int l, int r, ll h[][2]) {
  ll h0=(h[r][0]+mods[0]-h[l-1][0]*pow[0][r-l+1]%mods[0])%mods[0];
  ll h1=(h[r][1]+mods[1]-h[l-1][1]*pow[1][r-l+1]%mods[1])%mods[1];
  int t=hst.get(h0, h1);
  tree.ans[t]^=o-1;
}

void manacher(int n, char *s, PTree &tree, ll h[][2]) {
  static char str[2*maxn+3];
  static int d[2*maxn+1];
  str[0]='!';
  for (int i=1; i<=n; i++) {
    str[i*2-1] = '%', str[i*2]=s[i];
  }
  str[n*2+1] = '%';
  str[n*2+2] = '@';
  d[0] = 0;
  int maxp=0;
  for (int i=1; i<2*n; i++) {
    if (maxp+d[maxp]-1>=i) {
      d[i] = min(maxp+d[maxp]-i, d[maxp-i+maxp]);
    } else {
      d[i] = 1;
    }
    for (; i+d[i]<=2*n+2 && i>=d[i] && str[i+d[i]]==str[i-d[i]]; d[i]++);
    if (maxp+d[maxp]-1<i+d[i]-1) {
      maxp = i;
    }
    if (i%2==0 || d[i]>1) {
      addP(tree, i/2, (i-d[i]+2)/2, (i+d[i]-2)/2, h);
    }
  }
}

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  initPow(maxn);

  static char s[maxn+2];
  static ll hash[maxn+2][2];
  static PTree tree;
  int num;
  scanf("%d", &num);
  for (int ti=1; ti<=num; ti++) {
    tree.init();
    hst.init();
    scanf("%s", s+1);
    int len=strlen(s+1);
    for (int i=1, last=1; i<=len; i++) {
      last = tree.addChar(s, i, last);
    }

    initStrHash(len, s, hash);
    manacher(len, s, tree, hash);

    printf("%d\n", tree.solve());
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
